{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "### 题目描述\n",
        "\n",
        "[P1. Two Sum](https://leetcode.com/problems/two-sum/)\n",
        "\n",
        "Given an array of integers, return indices of the two numbers such that they add up to a specific target.\n",
        "\n",
        "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
        "\n",
        "Example:\n",
        "\n",
        "Given nums = [2, 7, 11, 15], target = 9,\n",
        "\n",
        "Because nums[0] + nums[1] = 2 + 7 = 9,\n",
        "return [0, 1].\n",
        "\n"
      ],
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 解题思路\n",
        "\n我是直接就暴搜了...就是两次循环，之后又优化了下，大体的思路是不变的，效果不太好。后面的优秀代码的思路很好。"
      ],
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Python代码[26.88%]"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def twoSum(self, nums, target):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :type target: int\n",
        "        :rtype: List[int]\n",
        "        \"\"\"\n",
        "        for i, num in enumerate(nums):\n",
        "            try:\n",
        "                j = i + 1 + nums[i+1:].index(target - num)\n",
        "            except ValueError:\n",
        "                pass\n",
        "            else:\n",
        "                return [i, j]\n",
        "            "
      ],
      "outputs": [],
      "execution_count": 1,
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-01-20T16:01:49.992296Z",
          "start_time": "2019-01-20T16:01:49.982847Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 测试\n",
        "s = Solution()\n",
        "s.twoSum([2, 7, 11, 15], 9)"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 2,
          "data": {
            "text/plain": [
              "[0, 1]"
            ]
          },
          "metadata": {}
        }
      ],
      "execution_count": 2,
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-01-20T16:02:48.272665Z",
          "start_time": "2019-01-20T16:02:48.250122Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 优秀代码学习[100%]"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def twoSum(self, nums, target):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :type target: int\n",
        "        :rtype: List[int]\n",
        "        \"\"\"\n",
        "        total = len(nums)\n",
        "        map_nums = {}\n",
        "        \n",
        "        for index, value in enumerate(nums):\n",
        "            complement = target - value\n",
        "            if complement in map_nums:\n",
        "                return [map_nums[complement], index]\n",
        "            map_nums[value] = index\n"
      ],
      "outputs": [],
      "execution_count": 3,
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-01-20T16:03:34.009448Z",
          "start_time": "2019-01-20T16:03:33.993119Z"
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 测试\n",
        "s = Solution()\n",
        "s.twoSum([2, 7, 11, 15], 9)"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 4,
          "data": {
            "text/plain": [
              "[0, 1]"
            ]
          },
          "metadata": {}
        }
      ],
      "execution_count": 4,
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-01-20T16:03:38.667289Z",
          "start_time": "2019-01-20T16:03:38.659790Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "有很多需要学习的地方，首先是`enumerate`的使用就不用说了，相比`range`加索引要好的多。然后代码效率搞的原因在其只进行了一次遍历，并且在每次遍历中“尽可能多地收集了有用的信息”。`complement`的引入使得问题由所谓的“求和”问题转化为“查找”问题，更关键的是`map_nums`的使用使得我们可以存储下来index的信息，方便找到数字组之后直接得到对应的index。"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [],
      "outputs": [],
      "execution_count": null,
      "metadata": {}
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "language": "python",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python",
      "version": "3.6.6",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "nteract": {
      "version": "0.12.3"
    },
    "toc": {
      "toc_position": {},
      "skip_h1_title": false,
      "number_sections": true,
      "title_cell": "Table of Contents",
      "toc_window_display": false,
      "toc_section_display": true,
      "title_sidebar": "Contents",
      "toc_cell": false,
      "nav_menu": {},
      "sideBar": true
    },
    "kernel_info": {
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}